package com.ztom.v2;

/**
 * @author ZhangTao
 */
public class Code99NextPermutation {

    public void nextPermutation(int[] nums) {
        int n = nums.length;
        // 从右向左找到第一个小于右侧相邻数字的数
        int index = n - 2;
        while (index >= 0 && nums[index] >= nums[index + 1]) {
            index--;
        }
        if (index >= 0) {
            // 找到了, 从右向左找到第一个比他大的数字
            int j = n - 1;
            while (j > index && nums[j] <= nums[index]) {
                j--;
            }
            swap(nums, index, j);
        }
        // 1. 没找到, 说明数组是倒序的
        // 2. 交换后, 右侧一定是倒序的
        reverse(nums, index + 1, n - 1);
    }

    public void reverse(int[] nums, int l, int r) {
        while (l < r) {
            swap(nums, l++, r--);
        }
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
